package com.leetcode.bfs;

import java.util.*;

public class Leetcode365 {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (targetCapacity < 0) {
            return true;
        }

        if (jug1Capacity + jug2Capacity < targetCapacity) {
            return false;
        }

        // 初始化
        State state = new State(0, 0);
        Queue<State> queue = new LinkedList<>();
        queue.offer(state);
        Set<State> isVisited = new HashSet<>();
        isVisited.add(state);

        while (!queue.isEmpty()) {
            State curState = queue.poll();

            int curX = curState.getX();
            int curY = curState.getY();

            if (curX == targetCapacity || curY == targetCapacity
                    || curX + curY == targetCapacity) {
                return true;
            }

            List<State> otherState = getOtherState(curX, curY, jug1Capacity, jug2Capacity);
            otherState.forEach(s -> {
                if (!isVisited.contains(s)) {
                    queue.offer(s);
                    isVisited.add(s);
                }
            });

        }
        return false;
    }

    private List<State> getOtherState(int curX, int curY, int jug1Capacity, int jug2Capacity) {
        List<State> states = new ArrayList<>(8);

        // 倒掉x y 中的水
        if (curX > 0) {
            states.add(new State(0, curY));
        }

        if (curY > 0) {
            states.add(new State(curX, 0));
        }

        // 倒满x y 中的水
        if (curX < jug1Capacity) {
            states.add(new State(jug1Capacity, curY));
        }

        if (curY < jug2Capacity) {
            states.add(new State(curX, jug2Capacity));
        }

        // x y 中的水相互倒
        // case1: 其中一个水杯能够装满
        if (curX + curY > jug1Capacity) {
            states.add(new State(jug1Capacity, curY - (jug1Capacity - curX)));
        }

        if (curX + curY > jug2Capacity) {
            states.add(new State(curX - (jug2Capacity - curY), jug2Capacity));
        }

        // case2: 其中一个水杯不能装满
        if (curX + curY < jug1Capacity) {
            states.add(new State(curX + curY, 0));
        }

        if (curX + curY < jug2Capacity) {
            states.add(new State(0, curX + curY));
        }
        return states;
    }

    public static void main(String[] args) {
        Leetcode365 demo = new Leetcode365();
        System.out.println(demo.canMeasureWater(3, 4, 5));
        System.out.println(demo.canMeasureWater(2, 6, 5));
    }
}

class State{
    private int x;

    private int y;

    public State(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        State state = (State) o;
        return x == state.x &&
                y == state.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return "State{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}
